home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / New System Software Extensions / OpenDoc A6 / OpenDoc Parts Framework / OPF / Found / BCCollec / Support / BCPool.cpp < prev    next >
Encoding:
Text File  |  1994-04-21  |  6.4 KB  |  246 lines  |  [TEXT/MPS ]
  1. //  The C++ Booch Components (Version 2.1)
  2. //  (C) Copyright 1990-1993 Grady Booch. All Rights Reserved.
  3. //
  4. //  Restricted Rights Legend
  5. //  Use, duplication, or disclosure is subject to restrictions as set forth 
  6. //  in subdivision (c)(1)(ii) of the Rights in Technical Data and Computer 
  7. //  Software clause at DFARS 252.227-7013. 
  8. //
  9. //  BCPool.cpp
  10. //
  11. //  This file contains the definitions for the heap storage management class.
  12.  
  13. #include "BCExcept.h"
  14. #include "BCPool.h"
  15.  
  16. union BC_UWord {
  17.   void* p; 
  18.   long double d; 
  19.   long l;
  20. };
  21.  
  22. BC_CPool::BC_CPool(size_t chunkSize)
  23.   : fHead(0), 
  24.     fUnusedChunks(0),
  25.     fChunkSize(BC_CPool::Align(chunkSize)),
  26.     fUsableChunkSize(BC_CPool::Align(chunkSize) - BC_CPool::Align(sizeof(BC_SChunk)))
  27. {
  28.   BC_Assert(fUsableChunkSize, BC_XStorageError("BC_CPool::BC_CPool", BC_kTooSmall));
  29. }
  30.  
  31. BC_CPool::~BC_CPool()
  32. {
  33.   PurgeUnusedChunks();
  34.   BC_SChunk* ptr = fHead;
  35.   while (ptr) {
  36.     BC_SChunk* chunk = ptr;
  37.     ptr = ptr->fNextSizedChunk;  
  38.     while (chunk) {
  39.       BC_SChunk* temp = chunk;
  40.       chunk = chunk->fNextChunk;
  41.       delete temp;
  42.     }
  43.   }
  44. }
  45.  
  46. void* BC_CPool::Allocate(size_t s) 
  47. {
  48.   size_t alignedSize = BC_CPool::Align(s);
  49.   if (!alignedSize)
  50.     return 0;
  51.   BC_Assert((alignedSize <= fUsableChunkSize),
  52.             BC_XStorageError("BC_CPool::Allocate", BC_kTooLarge));
  53.   BC_SChunk* temp;
  54.   BC_SChunk* previous = 0;
  55.   BC_SChunk* ptr = fHead;
  56.   while (ptr && (alignedSize > ptr->fElementSize)) {
  57.     previous = ptr;
  58.     ptr = ptr->fNextSizedChunk;
  59.   }
  60.   if (!ptr) {
  61.     ptr = GetChunk(alignedSize);
  62.     if (previous)
  63.       previous->fNextSizedChunk = ptr;
  64.     else
  65.       fHead = ptr;
  66.     ptr->fPreviousSizedChunk = previous;
  67.     ptr->fNextSizedChunk = 0;
  68.     ptr->fNextChunk = 0;
  69.   } else if ((alignedSize != ptr->fElementSize) || !ptr->fNextElement) {
  70.     temp = GetChunk(alignedSize);
  71.     if (previous)
  72.       previous->fNextSizedChunk = temp;
  73.     else
  74.       fHead = temp;
  75.     temp->fPreviousSizedChunk = previous;
  76.     if (alignedSize != ptr->fElementSize) {
  77.       ptr->fPreviousSizedChunk = temp;
  78.       temp->fNextSizedChunk = ptr;
  79.       temp->fNextChunk = 0;
  80.     } else if (!ptr->fNextElement) {
  81.       temp->fNextSizedChunk = ptr->fNextSizedChunk;
  82.       temp->fNextChunk = ptr;
  83.     }
  84.     ptr = temp;
  85.   }
  86.   BC_SElement* element = ptr->fNextElement;
  87.   ptr->fNextElement = element->fNextElement;
  88.   return (void*)element;
  89. }
  90.   
  91. void BC_CPool::Deallocate(void* p, size_t s)
  92. {
  93.   size_t alignedSize = BC_CPool::Align(s);
  94.   if (!alignedSize)
  95.     return;
  96.   BC_SChunk* ptr = fHead;
  97.   while (ptr && (alignedSize != ptr->fElementSize))
  98.     ptr = ptr->fNextSizedChunk;
  99.   BC_Assert((ptr != 0), BC_XStorageError("BC_CPool::Deallocate", BC_kMissing));
  100.   BC_SElement* element = (BC_SElement*)p;
  101.   element->fNextElement = ptr->fNextElement;
  102.   ptr->fNextElement = element;
  103. }
  104.  
  105. void BC_CPool::Preallocate(BC_Index numberOfChunks)
  106. {
  107.   for (BC_Index index = 0; (index < numberOfChunks); index++) {
  108.     BC_SChunk* chunk = (BC_SChunk*)(new char[fChunkSize]);
  109.     chunk->fNextChunk = fUnusedChunks;
  110.     fUnusedChunks = chunk;
  111.   }
  112. }
  113.  
  114. void BC_CPool::ReclaimUnusedChunks()
  115. {
  116.   BC_SChunk* chunk;
  117.   BC_SChunk* previous = 0;
  118.   BC_SChunk* ptr = fHead;
  119.   while (ptr) {
  120.     chunk = ptr;
  121.     while (chunk) {
  122.       chunk->fNumberOfElements = fUsableChunkSize / chunk->fElementSize;
  123.       chunk = chunk->fNextChunk;
  124.     }    
  125.     BC_SElement* element = ptr->fNextElement;
  126.     while (element) {
  127.       chunk = ptr;
  128.       while (chunk) {
  129.         if (((void*)chunk <= (void*)element) && 
  130.             ((void*)element < (void*)((char*)chunk + fChunkSize))) {
  131.           chunk->fNumberOfElements--;
  132.           break;
  133.         }
  134.         chunk = chunk->fNextChunk;
  135.       }
  136.       element = element->fNextElement;
  137.     }
  138.     BC_SChunk* previousChunk = 0;
  139.     chunk = ptr;
  140.     while (chunk) {
  141.       if (!chunk->fNumberOfElements) {
  142.         if (previousChunk) {
  143.           previousChunk->fNextChunk = chunk->fNextChunk;
  144.           chunk->fNextChunk = fUnusedChunks;
  145.           fUnusedChunks = chunk;
  146.           chunk = previousChunk->fNextChunk;
  147.         } else {
  148.           BC_SChunk* temp = chunk->fNextChunk;
  149.           BC_SChunk* next = chunk->fNextSizedChunk;
  150.           if (temp) {
  151.             if (previous)
  152.               previous->fNextSizedChunk = temp;
  153.             else
  154.               fHead = temp;
  155.             temp->fPreviousSizedChunk = previous;
  156.             temp->fNextSizedChunk = next;
  157.             temp->fNextElement = chunk->fNextElement;
  158.           } else {
  159.             if (previous)
  160.               previous->fNextSizedChunk = next;
  161.             else
  162.               fHead = next;
  163.           }
  164.           if (next) {
  165.             if (temp)
  166.               next->fPreviousSizedChunk = temp;
  167.             else
  168.               next->fPreviousSizedChunk = previous;
  169.           }
  170.           chunk->fNextChunk = fUnusedChunks;
  171.           fUnusedChunks = chunk;
  172.           chunk = temp;
  173.         }
  174.       } else {
  175.         previousChunk = chunk;
  176.         chunk = chunk->fNextChunk;
  177.       }
  178.     }
  179.     previous = ptr;
  180.     ptr = ptr->fNextSizedChunk;
  181.   }
  182. }
  183.  
  184. void BC_CPool::PurgeUnusedChunks()
  185. {
  186.   while (fUnusedChunks) {
  187.     BC_SChunk* chunk = fUnusedChunks;
  188.     fUnusedChunks = chunk->fNextChunk;
  189.     delete chunk;
  190.   }
  191. }
  192.  
  193. BC_Index BC_CPool::NumberOfDirtyChunks() const
  194. {
  195.   BC_Index count = 0;
  196.   BC_SChunk* ptr = fHead;
  197.   while (ptr) {
  198.     BC_SChunk* chunk = ptr;
  199.     ptr = ptr->fNextSizedChunk;  
  200.     while (chunk) {
  201.       count++;
  202.       chunk = chunk->fNextChunk;
  203.     }
  204.   }
  205.   return count;
  206. }
  207.  
  208. BC_Index BC_CPool::NumberOfUnusedChunks() const
  209. {
  210.   BC_Index count = 0;
  211.   BC_SChunk* chunk = fUnusedChunks;
  212.   while (chunk) {
  213.     count++;
  214.     chunk = chunk->fNextChunk;
  215.   }
  216.   return count;
  217. }
  218.  
  219. BC_CPool::BC_SChunk* BC_CPool::GetChunk(size_t s)
  220. {
  221.   BC_SChunk* chunk;
  222.   if (fUnusedChunks) {
  223.     chunk = fUnusedChunks;
  224.     fUnusedChunks = chunk->fNextChunk;
  225.   } else {
  226.     chunk = (BC_SChunk*)(new char[fChunkSize]);
  227.     BC_Assert((chunk != 0), BC_XStorageError("BC_CPool::GetChunk", BC_kOutOfMemory));
  228.   }
  229.   chunk->fElementSize = s;
  230.   chunk->fNumberOfElements = fUsableChunkSize / s;
  231.   char* start = (char*)chunk + Align(sizeof(BC_SChunk));
  232.   char* stop = &start[(chunk->fNumberOfElements - 1) * chunk->fElementSize];
  233.   for (char* element = start; (element < stop); element += s)
  234.     ((BC_SElement*)element)->fNextElement = (BC_SElement*)(element + s);
  235.   ((BC_SElement*)stop)->fNextElement = 0;
  236.   chunk->fNextElement = (BC_SElement*)start;
  237.   return chunk;
  238. }
  239.  
  240. size_t BC_CPool::Align(size_t s)
  241. {
  242.   size_t alignedSize = s + sizeof(BC_UWord) - 1;
  243.   alignedSize -= alignedSize % sizeof(BC_UWord);
  244.   return alignedSize;
  245. }
  246.